今天的題單：

• Longest Palindrome

• Reverse Linked List

409. Longest Palindrome

這題要問一個 string 裡的字母可以組成最長回文的長度。

思路：

• 統計所有出現子母的次數

• 所有出現次數 >= 2 的字母都可以取出 2n 個的組成回文，總長為 max_len

• 看有沒有剩餘的字母，有的話回文長度為 max_len +1，否則就是 max_len

針對第三步，由於只要次數是奇數就一定會有剩，所以可以在第二步的時候檢查是否有奇數，節省一個 loop 的時間。

class Solution {
public:
    int longestPalindrome(string s) {
        map<char, int> m;

        for (char& c: s) {
            if (m.find(c) == m.end()) {
                m[c] = 1;
            } else {
                m[c]++;
            }
        }

        int max_len = 0;
        int num_even = 0;
        bool has_odd = false;

        map<char, int>::iterator it;
        for (it = m.begin(); it != m.end(); it++) {
            if (it->second >= 2) {
                max_len += (it->second / 2) * 2;
                it->second = it->second % 2;
            }
            if (it->second > 0) {
                has_odd = true;
            }
        }

        return has_odd ? max_len + 1 : max_len;
    }
};

loop 再簡化：

for (it = m.begin(); it != m.end(); it++) {
    if (it->second % 2 == 0) {
          max_len += it->second;
      } else {
          max_len += it->second - 1;
          has_odd = true;
      }
}

206. Reverse Linked List

直觀的一個一個 node 把 edge 反轉，需要思考的是實作方式。

我的第一個 attempt 是 iterative 的方法：

• 使用兩個 pointer，p1 指在第一個 node，p2 指在第二個 node，還需要一個 pointer tmp 記住 p1 前一個 node

  • 每個 iteration

    1. 把 p1 的 next 接到前一個 node

    2. pointer 各往下移一個 node

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* p1 = head;
        ListNode* tmp = NULL;

        if (p1 == nullptr)
            return p1;
        
        ListNode* p2 = p1->next;    // p2 goes to the next node
        
        while (p2 != nullptr) {
            p1->next = tmp;             // reverse the pointer of p1
            tmp = p1;                   // record p1
            p1 = p2;                    // p1 goes to the next node
            p2 = p2->next;              // p2 goes to the next node
        }

        // the last node
        p1->next = tmp;             // reverse the pointer of p1

        return p1;

    }
};

自己在寫的時候想的沒有很清楚，Leetcode sample code 寫得更清楚一點，一共需要三個 pointer 指向 previous, current, after 三個 node。每次 iteration 要更改 current node 的 next 指向。

// Leetcode sample code
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // three pointers prev cur after ; 
        // swap connection cur prev and shift next ;
        ListNode * prev = nullptr ;
        ListNode * cur = head ;
        if (cur == NULL) { 
            return head; 
        }
        ListNode * after = head -> next ; 
        while (cur != NULL){
            cur->next = prev;
            prev = cur;
            cur = after;

            if (after == NULL) {
                break; 
            }
            after = after->next;
        }
        return prev;        
    }
};

Follow-up: recursive 實作

從最後一對 node 開始反轉 edge，一開始走到最後一個 node 的時候返回自己，recursive 結束後除了 edge 都反轉完，也拿到 reverse linked list 的 head。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr)
            return head;

        ListNode* new_head = reverseEdge(head, head->next);
        
        head->next = NULL;
        
        return new_head;
    }

    ListNode* reverseEdge(ListNode* node, ListNode* next_node) {
        if (node->next == nullptr) {
            return node;
        }
        ListNode* new_head = reverseEdge(node->next, next_node->next);
        next_node->next = node;

        return new_head;
    }
};